Day4. 陣列(Array) - 題目實作(上)

15th鐵人賽

雜食性的貓

2023-09-19 22:45:26

354 瀏覽

分享至

今日看板圖，排排站的狗狗，是不是很像陣列連在一起的感覺呢？
如昨天所說，今天會舉一些題目來看實際算法怎麼寫，我會條列步驟，並列出對應的 C# 程式碼。如果你是想練習的，建議可以先自己看了是和哪個算法相關，先自己想過你會怎麼套，嘗試自己寫寫寫看。如果卡住再看我的條列步驟，還是卡住，就再參考實際程式碼。

無論如何，建議有時間一定要自己手寫過，懂概念跟實際手寫過是差很多的，演算法中總有很多細小的坑，只有踩過的人才會知道要注意那個洞。
好地、那讓我們來開始今天的練習吧。

雙指針

快慢指針

Remove Element
這題是要在單次走訪的時候移除全部指定元素，假設長度為 n，有 k個元素要移除，則題目會檢查前面到 n - k 位置，是否按照本來的相對位置排序，不管後面 k 個是什麼。

兩個指針同時指向索引 0 的位置
快指針負責主要遍歷陣列，慢指針負責標示如果要替換時，哪個元素可以被換掉，慢指針(不含指針本身)前面的元素都是已經檢查過、非被移除元素的對象
所以迴圈的終止條件是快指針完整遍歷完陣列
核心思想是我們不在意被移除的元素要去哪，我們只要找需要的元素放到前 n - k 位置就好
先判斷當前快指針指向的元素，是不是要留下的元素(非目標元素)，如果不是，快指針自己往前走
如果是要留下的元素，把該元素換到慢指針的位置(前 n-k 個)保留下來，快慢指針一同前進
就這樣持續讓快指針前進進行 5. 6.步直到陣列被遍歷，這時前 n-k 個保留下的元素就是非目標元素

以 [3,2,2,3]，移除 3 為例，一開始都指向位置 0，
慢指針 0，快指針繼續往前找到第一個不用移除的元素 index 1 = 2，快慢指針的數字交換 [2,3,2,3]
慢指針 1，快指針找到第二個不用移除的元素 index 2 = 2，快慢指針的數字交換 [2,2,3,3]
快指針走訪完剩下的陣列，沒有其他不用移除(要留下)的元素了
回傳 [2,2,3,3]，因為有 2 個 3，長度為 4，只檢查前 4 - 2 = 2 個元素，[2,2,,]，符合

public class Solution {
    public int RemoveElement(int[] nums, int val) {
        var slow = 0;
        var fast = 0;
        while(fast < nums.Length)
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}

經典的快慢指針題目，不用快慢指針的暴力解是用兩層迴圈，第一層找需要移除的元素，找到後把那個位置後面的元素全部往前移動一格(第二層)。透過快慢指針的方式，反過來想只找要留下的元素，能夠同時在空間複雜度 O(1) 且時間複雜度 O(n) 的狀況下解決這個問題。

左右指針

Two Sum II Input array is sorted
給你一個排序後的一維陣列，以及一個目標數，找出唯一一組陣列中兩個索引指向的元素，相加起來會正好等於目標數。
因為是排序過的陣列，左邊最小，右邊最大理論上我們從兩側開始收縮，只要存在一組答案，一定能夠找到目標。
1.定義兩個指針，分別指向開頭和結尾的索引位置
2.將兩個指針指向的元素相加，和目標數比對
3.如果目標數 = 元素相加，回傳左右兩個指針的位置，找到答案
4.如果目標數 > 元素相加，表示左指針(從小開始遍歷)要往右走一格(會讓總和變大)
5.如果目標數 < 元素相加，表示右指針(從大開始遍歷)要往左走一格(會讓總和變小)
6.回到步驟 2. ，因為題目說一定會有一組解，持續重複到找到答案為止

public class Solution {
    public int[] TwoSum(int[] numbers, int target) {
        var left = 0;
        var right = numbers.Length - 1;
        while(left < right)
        {
            var twoSum = numbers[left] + numbers[right];
            if(twoSum == target)
            {
                return new[] {left + 1, right + 1};//題目問第幾個元素，從1開始，所以這邊要加1
            }
            if(twoSum < target)
            {
                left++;
            }
            if(twoSum > target)
            {
                right--;
            }
        }
        throw new NotSupportedException();
    }
}

考慮到使用左右指針的時機，通常一樣是有序陣列，讓指針分別從左右收縮的這個行為有意義。

滑動窗口

Minimum Size Subarray Sum
滑動窗口的概念其實跟雙指針有關聯，取而代之的是雙指針關注的是指針指向的標的，而滑動窗口則是關注維護的兩個指針中間形成的連續區段。
這題給了我們一個全為正數的陣列和一個目標數，讓我們回傳一個最短的子陣列(陣列中連續元素形成、最短長度為1，最長等同父陣列的陣列稱做子陣列)，且該子陣列的和大於目標數。
1.維護兩個指針，一左一右，兩個指針中間形成的空間即為符合題目定義的區間：總和大於目標數
2.用另一個變數 sum 來累計目前區間內的總合，避免每次都要重新遍歷一次區間以得到總合
3.迴圈開始遍歷，遍歷時進行判斷：目前累計的 sum 是否大於目標數
4.如果 sum >= 目標數，表示我們可以收窄左側的邊界(左指針)，來看看用更少的元素是否還是能大於目標元素(下一迴圈)，同時更新 sum
5.如果 sum < 目標數，表示目前窗口內的元素總合尚未達到條件，擴增右側邊界(右指針)，以讓窗口內元素增加，同時更新 sum

但是如果右邊邊界已經到底，但目前窗口元素總和仍不到目標數，右邊無法增加元素的情況下，收窄左邊已經無意義(總和只會變小)，結束迴圈
6.當 4. 或 5. 拓增了元素以後，回到3. 重新檢查更新後的 sum 是否符合條件

public class Solution {
    public int MinSubArrayLen(int target, int[] nums) {
        var left = 0;
        var right = 1;
        var sum = nums[0];
        var minDistance = 0;
        var currentDistance = 0;
        while(true){
            if(sum < target){
                if(right >= nums.Length){
                    break;
                }
                sum += nums[right];
                right++;
            }
            else{
                sum -= nums[left];
                currentDistance = right - left;
                minDistance = minDistance > currentDistance || minDistance == 0 ? currentDistance : minDistance;
                left++;
            }
        }
        return minDistance;
    }
}

看到要取符合條件的子陣列其實就可以思考看看滑動窗口合不合適，滑動窗口專門就是在解決取一個陣列中滿足特定條件的子陣列這類問題的。

本來想把昨天提到所有陣列的內容放在今天一篇，但是發現篇幅會過長，希望提到的題目最多大概在 3 - 5 題，對讀者和我(XD)的負擔都會比較小。剩下的算法我們會放在明天繼續和大家分享相關題目。

另外，當你在 Leetcode 提交並通過題目後，Leetcode 會建議一些相關類似題目在圖中框起來的 More Challenges，如果有時間，同一個主題建議再多做 2、3 題，可以確認自己是不是真的懂了那個演算法的概念。真的做不出來，Leetcode 的 Solutions 大部分的題目也都有其他人分享的解析，可以在真的思考後、卡住的時候再去參考別人的寫法，比較跟自己的解法差在哪裡，是哪裡有問題。

如果你是後來才來回顧的，不用特別重新 Submit 一次來看有哪些相似問題，問題頁往下拉，Similar Questions 或 Related Topics 都能幫助你找到相關 / 特定主題的題目。